package com.hanxiaozhang.no10leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一棵二叉树和一个sum值，找到所有从根到叶子的路径，使得其路径上的节点和等于所给的sum值，
 * 返回所有可能的路径结果〉
 *
 * @author hanxinghua
 * @create 2024/4/12
 * @since 1.0.0
 */
public class No113PathSumII {


    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(5);
        tree1.left = new TreeNode(4);
        tree1.right = new TreeNode(8);
        tree1.left.left = new TreeNode(11);
        tree1.right.left = new TreeNode(13);
        tree1.right.right = new TreeNode(4);
        tree1.left.left.left = new TreeNode(7);
        tree1.left.left.right = new TreeNode(2);
        tree1.right.right.right = new TreeNode(1);

        System.out.println(method1(tree1, 22));

    }

    /**
     * 方法1：参考 No112PathSum.method1()
     *
     * @param root
     * @param sum
     * @return
     */
    private static List<List<Integer>> method1(TreeNode root, Integer sum) {
        List<List<Integer>> results = new ArrayList<>();
        if (root == null) {
            return results;
        }
        List<Integer> result = new ArrayList<>();
        Integer curSum = 0;

        backtrack(results, result, sum, curSum, root);

        return results;
    }

    private static void backtrack(List<List<Integer>> results, List<Integer> result, int sum, int curSum, TreeNode root) {

        // 添加元素
        result.add(root.val);
        curSum += root.val;

        // 边界条件，判断当前是否为叶子节点 Tips:一开始没有想到
        if (root.left == null && root.right == null) {
            if (sum == curSum) {
                results.add(new ArrayList<>(result));
            }
            // 恢复现场
            result.remove(result.size() - 1);
            // 这里没啥用
            // curSum -= root.val;
            return;
        }

        if (root.left != null) {
            backtrack(results, result, sum, curSum, root.left);
        }
        if (root.right != null) {
            backtrack(results, result, sum, curSum, root.right);
        }
        // 恢复现场
        result.remove(result.size() - 1);
        curSum -= root.val;
    }


}
